package main

import (
	"fmt"
	"math"
)

func main() {
	arr := []int{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}
	fmt.Println(GetMaxConsecutiveOnes(arr, 2))

	arr = []int{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}
	fmt.Println(GetMaxConsecutiveOnes(arr, 3))
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param arr int整型一维数组
 * @param k int整型 允许0变为1的个数
 * @return int整型
 */
func GetMaxConsecutiveOnes(arr []int, k int) int {
	// write code here
	maxSize := math.MinInt32
	N := len(arr)

	var f func(idx int)
	f = func(idx int) {
		if idx == N {
			maxSize = max(right(arr, idx-1), maxSize)
			return
		}
		if k == 0 {
			fmt.Println(arr)
			if arr[idx] == 1 {
				maxSize = max(left(arr, idx-1)+right(arr, idx), maxSize)
			} else {
				maxSize = max(left(arr, idx-1), maxSize)
			}
			return
		}
		// 不修改
		f(idx + 1)

		if arr[idx] == 0 {
			// 修改
			k--
			arr[idx] = 1
			f(idx + 1)
			arr[idx] = 0
			k++
		}
	}

	f(0)
	return maxSize
}

func left(arr []int, idx int) int {
	sum := 0
	for idx >= 0 && arr[idx] == 1 {
		sum++
		idx--
	}

	return sum
}

func right(arr []int, idx int) int {
	sum := 0
	for idx < len(arr) && arr[idx] == 1 {
		sum++
		idx++
	}

	return sum
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}
